package com.zjsru.plan2025.oneday;

/**
 * 1922. 统计好数字的数目
 *
 * @Author: cookLee
 * @Date: 2025-04-13
 */
public class CountGoodNumbers {

    /**
     * 主
     * \
     * 输入：n = 1
     * 输出：5
     * 解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。
     * \
     * 输入：n = 4
     * 输出：400
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        CountGoodNumbers countGoodNumbers = new CountGoodNumbers();
        int n = 4;
        System.out.println(countGoodNumbers.countGoodNumbers(n));
    }

    long MOD = 1000000007;

    public int countGoodNumbers(long n) {
        //偶数最多0，2，4，6，8 奇数最多1，3，5，7，9
        return (int) (this.helper(5, (n + 1) / 2) * (int) this.helper(4, n / 2) % this.MOD);
    }

    /**
     * 帮手
     * 快速幂求出 x^y % mod
     *
     * @param x x
     * @param y y
     * @return long
     */
    private long helper(int x, long y) {
        long res = 1;
        long mul = x;
        while (y > 0) {
            if (y % 2 == 1) {
                res = res * mul % this.MOD;
            }
            mul = mul * mul % this.MOD;
            y /= 2;
        }
        return res;
    }
}
